1. Field of the Invention
The present invention relates to a document analysis system that generates a general solution for identifying a digital image of a document and fields or informational elements within the document.
2. Description of the Prior Art
The ability to automate the process of data extraction from digital images of paper greatly increases the productivity and capacity of any business. By automating the data entry process, operating costs can be reduced due to reduced manpower requirements and capacity can be increased by maximizing the throughput of data entry operations. In businesses such as banking, there is a need for high speed processing of all types of documents. Banks usually receive many types of documents that must be entered into computers. In addition new services can be offered by automating data extraction from documents. As an example, extending Automatic Teller Machines (ATM) capabilities to include document processing would allow customers to cash checks and receive funds back from the ATM. In the retail business there is a need to capture information from a customer at the point of sale. The information to be extracted could be from the customer's check or from his identification card (i.e. driver's license). Other applications for this invention is in wholesale and retail lockboxes. The more automated the process for handling payments, the lower the operating costs and the sooner the payments are credited.
To provide a robust solution, the system must be capable of processing a mixed stream of document types. Also, the system must be capable of processing fixed format documents as well as highly unconstrained documents.
To use a document analysis system the document is first scanned using one of several existing techniques such as a charged coupled device (CCD) to create a digital image representing a matrix of the black and white points on the page by a matrix of 0's and 1's. This matrix is then transmitted to a digital computer where it can be processed, displayed, identified and stored.
The requirements for processing the scanned document can be divided into two types: identification and decomposition of constrained documents and identification and decomposition of unconstrained documents.
The identification of constrained documents has been solved for various document types. For example the DP-ATM Model 5665 system produced by NCR in Dundee, Scotland, the HITC form identification system, available from NCR in Atlanta and the FIRST system developed by Quest, a division of Lucent Technologies are three systems that identify and process constrained documents. These systems classify the document as a specific type and then invoke an identification subsystem to process the type of document identified.
For unconstrained documents, some systems do locate and read specified fields. For example, to find the courtesy amount some systems search a designated area for a `$` character. However, in many cases a `$` may not be present in the field and the courtesy amount may not be within the area designated. Furthermore, these systems may not have the capability of locating other fields that are not clearly delineated. These systems include the Courtesy Amount Locator (CAL) by Quest, a division of Lucent Technologies, and Scaleable Image Item Processing System (SIIPS) available from NCR, Waterloo, Canada. Other systems attempt a trial-by-error approach. These systems search for the field in a list of locations ranked by probability of success. This brute force approach is inaccurate and inefficient as it requires a large amount of processing resources. Furthermore, these systems cannot interpret data from different document types, i.e., checks, deposit slips, and miscellaneous financial documents. All these existing systems focus on a specific task and do not analyze the overall structure of the document to derive a solution.
While it may be possible to search for a field, for example the courtesy amount, by processing each and every print field on the right side of the document, this results in a waste of processing resources since a large region of the scanned image must be searched and the region may include a large number of fields. Therefore, one of the problems that exist today in document analysis is to create a system that determines what information is useful in generating a solution for identifying a document and fields within the document. This solution would be based on information gathered from the scanned image, as well as the computational cost involved in generating the solution.